Introduction to Machine Learning

1. Introduction

This unit examines the most widely used partitional clustering algorithm: K-Means Clustering. We first examine its optimization objective and two-step (assignment + update) procedure, then consider the initialization problem and two ways to address it: multiple restarts and Bisecting K-Means. We then turn to evaluation measures: Within/Between Sum of Squares, the Elbow Curve, and the Silhouette Coefficient.

Today's Agenda

1. Recap of the Previous Lecture
2. K-Means algorithm and objective
3. Choosing Initial Centroids & Initialization sensitivity
4. Bisecting K-Means
5. Clustering Evaluation: Intrinsic Measures
6. Within & Between Sum of Squares (WSS, BSS, TSS)
7. Elbow / Scree Plot
8. Silhouette Coefficient and average silhouette width
9. Extrinsic measures: Purity, Rand Statistic (RI), Jaccard Coefficient

2. Theory

2.1 K-Means Objective: Within-Cluster Sum of Squares

K-Means partitions n data points into K clusters. During the assignment step, each point is assigned to the cluster with the nearest centroid (mean). The overall objective is to minimize the Within-Cluster Sum of Squares (WSS), also called the Sum of Squared Errors (SSE):

where:

• \( K \) = number of clusters (must be specified in advance)
• \( C_i \) = the i-th cluster (set of assigned points)
• \( \mu_i \) = centroid (mean) of cluster i: \( \mu_i = \frac{1}{|C_i|}\sum_{x\in C_i} x \)
• \( x \) = a single data point (vector)
• \( \|\cdot\|^2 \) = squared Euclidean distance

Intuition: The goal is to find K centroids so that points are close to the centroids of the clusters to which they are assigned. K-Means is an iterative optimization algorithm: it starts with K initial centroids and alternates between two steps until convergence.

2.2 K-Means Algorithm Step-by-Step

1. Input: Dataset \( D = \{x_1, x_2, \dots, x_n\} \), number of clusters K.
2. Output: K clusters and their centroids.
3. 1. Initialize: Select K initial centroids \( \{\mu_1, \mu_2, \dots, \mu_K\} \) (randomly or via heuristic).
4. 2. Repeat until convergence:
5.    a) Assignment step: For each point \( x_i \), assign it to cluster \( j^* = \arg\min_j \| x_i - \mu_j \|^2 \).
6.    b) Update step: For each cluster \( C_j \), recompute its centroid \( \mu_j = \frac{1}{|C_j|} \sum_{x \in C_j} x \).
7. 3. Convergence criteria (any of): Centroids do not change (or change < threshold), the maximum number of iterations is reached, or WSS does not decrease significantly.

2.3 The Initialization Problem

K-Means is very sensitive to the choice of initial centroids because it finds a local optimum, not necessarily the global optimum. As a result, different starting points can produce different final clusterings. Poor initialization can produce:

• Suboptimal cluster assignments (higher WSS)
• Empty clusters (if a centroid never wins any point)
• Slow convergence (centroids wander before settling)

2.4 Solutions to the Initialization Problem

2.5 Bisecting K-Means Algorithm

1. Initialize: Place all data points in a single cluster.
2. Repeat until K clusters are obtained:
3.    a) Select cluster to split: Choose by one of:
   • Largest WSS / SSE (most internal variance)
   • Largest number of data points
   • Random selection (less common)
4.    b) Bisect the selected cluster:
   • Run basic K-Means with K=2 on the selected cluster.
   • Perform multiple trials with different random initializations.
   • Keep the bisection with lowest total SSE.
5.    c) Update cluster list: Remove the original cluster; add the two sub-clusters.
6. Terminate when the desired K is reached.

2.6 Evaluating Clustering Results

Evaluating clustering is more difficult than evaluating supervised learning because there is no single "right answer." Instead, the goal is to compare different clustering experiments and select a good configuration. Two families of measures are used:

2.7 Internal Measures: Cohesion vs Separation

• Cluster Cohesion: How closely related are the objects inside a cluster? It is measured by Within-Cluster Sum of Squares (WSS).
• Cluster Separation: How well-separated is one cluster from the other clusters? It is measured by Between-Cluster Sum of Squares (BSS).

For the formal definitions, let \(|C_i|\) denote the size of cluster \(i\), \(m_i\) its centroid, and \(m\) the overall (global) mean of all data points.

Key identity: Total Sum of Squares TSS = WSS + BSS for any partition. Because the dataset is fixed, TSS is constant even when the partition changes.

2.8 Cohesion & Separation: Numerical Example

2.9 Elbow / Scree Plot

To choose K, vary the number of clusters and plot total within-cluster SSE against K. Look for an elbow: the point after which the drop in WSS becomes much smaller. This elbow represents a good balance between explanatory power (low WSS) and model simplicity (small K).

Caution: Sometimes there is no clear elbow. Even when one is visible, interpreting it and deciding on K remain somewhat subjective.

2.10 Silhouette Coefficient

The Silhouette Coefficient evaluates each point individually by comparing how well it fits within its own cluster with how separated it is from the other clusters. It works with any distance metric.

For each point \(d_i\) currently assigned to cluster \(C_i\):

1. Compute \(a_i\): the average dissimilarity (distance) of \(d_i\) to all other objects in the same cluster \(C_i\). Small \(a_i\) is good: the cluster is tight/homogeneous.
2. For every other cluster \(C_j\) (\(j \neq i\)), compute the average distance from \(d_i\) to all objects in \(C_j\). The minimum of these averages is called \(b_i\): \[ b_i = \min_{j \neq i} \text{avg}_{x \in C_j} d(d_i, x) \] \(b_i\) tells us how close \(d_i\) is to the nearest competing cluster. Larger is better!
3. Point silhouette for \(d_i\):
   \[ s(i) = \frac{b_i - a_i}{\max(a_i, b_i)} \]

Interpretation of s(i)

Aggregate Silhouette Summaries

• Per-cluster average silhouette width: \[ \bar{s}(C_j) = \frac{1}{|C_j|} \sum_{d_i \in C_j} s(i) \] Wider is better (cluster 1 "better" than cluster 2 in the lecture figure).
• Global average silhouette width: \[ \text{ASW} = \frac{1}{n} \sum_{i=1}^{n} s(i) \] Typically maximized over K to pick the number of clusters.

Cost: Silhouette requires O(n²) distance evaluations — computationally expensive for larger datasets.

How Silhouette Changes with Wrong K

• K too high: Natural clusters get split into sub-clusters. Those sub-clusters are still homogeneous (low a_i) but very close to each other (low b_i too) → s(i) shrinks towards 0.
• K too low: Separate natural clusters get merged. Within-cluster a_i grows because unrelated points share a centroid → again s(i) shrinks toward 0 or negative.
• Right K: Each natural cluster = one cluster. High separation between clusters → high b_i. Tight within clusters → low a_i. → s(i) peaks near +1.

2.11 Extrinsic Clustering Evaluation Measures

Extrinsic measures require ground-truth labels and compare the generated clustering with those labels. They allow direct comparison of clustering algorithms on benchmark datasets where labels are available. We cover three measures: Purity, Rand Index, and Jaccard.

2.12 Purity Contingency Table Example

6 clusters × 6 ground-truth labels on a news-like dataset (3,204 documents):

For each cluster row, take the maximum and divide by n:

2.13 Rand Index Calculation: 5-Point Worked Example

Consider five data points: p1, p2, p3, p4, p5.
The produced clustering is C1 = {p1, p2, p3}, C2 = {p4, p5} (two clusters).
The true labels are L1 = {p1, p2}, L2 = {p3, p4, p5} (two classes).

The total number of distinct pairs is C(5,2) = 10.

Counts: TP = 2, TN = 5, FP = 2, FN = 1. Total 10.

3. Interactive Examples

4. Numerical Solutions

5. Try It Yourself

6. Interactive Quiz